package 剑指;

import java.util.LinkedList;
import java.util.Queue;

public class offer26 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x;}
    }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 空树不是任何树的子结构 -> B 不能为 null
        // 此时A为空了 也就是false了
        if (A == null || B == null) return false;
        // 1. 要么以根节点为A的子树 包含B
        // 2. 要么B树是A的左子树
        // 3. 要么B树是A的右子树
        return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    public boolean isSameTree(TreeNode A,TreeNode B) {
        if (B == null) return true;
        if (A == null) return false;
        if (A.val != B.val) return false;
        return isSameTree(A.left, B.left) && isSameTree(A.right, B.right);
    }
}
